package com.demo.java.OD401_450.OD414;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【生成哈夫曼树(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146256696
 */
public class OdMain {
    static class Node implements Comparable<Node> {
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }

        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.value, other.value);
        }
    }

    // 构建Huffman树
    public static Node buildHuffmanTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            nodes.sort(Node::compareTo);  // 对节点进行排序
            Node newNode = new Node(nodes.get(0).value + nodes.get(1).value);
            newNode.left = nodes.remove(0);  // 取出最小的两个节点
            newNode.right = nodes.remove(0);
            nodes.add(newNode);  // 将新节点加入列表
        }
        return nodes.get(0);  // 返回树的根节点
    }

    // 中序遍历
    public static void inorderTraversal(Node root, List<Integer> result) {
        if (root != null) {
            inorderTraversal(root.left, result);  // 遍历左子树
            result.add(root.value);  // 访问根节点
            inorderTraversal(root.right, result);  // 遍历右子树
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入节点数量
        int n = scanner.nextInt();
        List<Node> nodes = new ArrayList<>();

        // 输入节点的值
        for (int i = 0; i < n; i++) {
            nodes.add(new Node(scanner.nextInt()));
        }

        // 构建Huffman树
        Node root = buildHuffmanTree(nodes);

        // 中序遍历树并输出结果
        List<Integer> result = new ArrayList<>();
        inorderTraversal(root, result);
        System.out.println(String.join(" ", result.stream().map(String::valueOf).toArray(String[]::new)));
    }
}
